package com.ljc;

import com.ljc.dto.TreeNode;

/**
 * @author clj
 * @date 2022/12/5
 * @desc
 * Given the root of a binary tree, return its maximum depth.
 *
 * A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
 *
 * Example 1:
 * Input: root = [3,9,20,null,null,15,7]
 * Output: 3
 *
 * Example 2:
 * Input: root = [1,null,2]
 * Output: 2
 */
public class E104MaxDepthOfBinaryTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

//        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);

        int maxDepth = maxDepth(root);
        System.out.println(maxDepth);
    }

    /**
     * 方法一：深度优先搜索
     * 思路与算法
     *
     * 如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max(l,r)+1
     * 而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。
     * 具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。
     * 递归在访问到空节点时退出。
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
//        System.out.println("TreeNode: " + root);
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
//            System.out.println("root.left: " + root.left);
            int rightHeight = maxDepth(root.right);
//            System.out.println("root.right: " + root.right);
//            System.out.println("leftHeight: " + leftHeight);
//            System.out.println("----------------");
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

}
